/******************************************************************************
 * Copyright (C) 2009 Peter ZHOU <peterzhoulei@gmail.com>                     *
 *                                                                            *
 * This program is free software; you can redistribute it and/or              *
 * modify it under the terms of the GNU General Public License as             *
 * published by the Free Software Foundation; either version 2 of             *
 * the License, or (at your option) any later version.                        *
 *                                                                            *
 * This program is distributed in the hope that it will be useful,            *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of             *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              *
 * GNU General Public License for more details.                               *
 *                                                                            *
 * You should have received a copy of the GNU General Public License          *
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.      *
 ******************************************************************************/

#import "ddIM_tree.h"
#import "ddIM_word.h"

@implementation ddIM_tree

-(id)init
{
	self = [super init];
	head = [[ddIM_wordList alloc] init];
	[head setFatherNode:nil];
	[head setWord:[[NSMutableArray alloc] init]];
	_candidatesPhases = [[NSMutableArray alloc] init];
	_candidatesPY = [[NSMutableArray alloc] init];
	return self;
}

-(void)addWord:(id)node:(NSString*)py:(NSString*)str:(NSInteger)freq:(NSMutableArray*)preWords
{
	NSInteger i;
	bool objectAdded = false;
	id newWord = [[ddIM_word alloc] init];
	NSString* wordstr = [NSString stringWithString:str];
	[newWord setWordstr:wordstr];
	[newWord setFreq:freq];
	[newWord setPrevWord:preWords];
	//TODO: implement prev word link
	for (i = 0; i<[[node word] count]; i++)
	{
		if ( freq > [[[node word] objectAtIndex:i] freq] )
		{
			[[node word] insertObject:newWord atIndex:i];
			objectAdded = true;
			break;
		}
	}
	if (!objectAdded) //if it is the smallest one, add it to the bottom
		[[node word] addObject:newWord];
}

-(id)insertNode:(id)parent:(NSString*)py:(NSString*)str:(NSInteger)freq:(NSMutableArray*)preWords
{
	ddIM_wordList* node;
	node = [[ddIM_wordList alloc] init];
	[node setPy:py];
	if ( str != nil )
	{
		[self addWord:node:py:str:freq:preWords];
	}
	[node setFatherNode:parent];
	[[parent childList] addObject:node];
	if ( [parent isEqualTo:head] )
		[_candidatesPY addObject:py];
	return node;
}

-(bool)insertWord:(NSArray*)py:(NSString*)str:(NSInteger)freq:(NSMutableArray*)preWords
{
	NSInteger level = 0;
	ddIM_wordList* wordNode;
	NSString* nodepy;
	bool foundNode;
	id currentNode;
	currentNode = head; //search from the head
	for ( nodepy in py )
	{
		foundNode = false;
		//search from the first char to the last
		for ( wordNode in [currentNode childList] )
		{
			
			if ( [nodepy compare:[wordNode py]] == 0 )			
			{
				//found Node
				foundNode = true;
				currentNode = wordNode;
				if ( level == [str length] - 1 ) //add the new word, if the word ends
				{
//					NSLog(str);
					[self addWord:wordNode:py:str:freq:preWords];
				}
				break;
			}
		}
		if ( !foundNode ) //if node not found, add new node to the tree
		{
			//insertNode
			if ( level != [str length] - 1 ) //if it is not the end of the string
				currentNode = [self insertNode:currentNode:nodepy:nil:0:preWords];
			else
				[self insertNode:currentNode:nodepy:str:freq:preWords];
		}
		level++;
	}
	return true;
}
/*
//can only be deleted from the last level
-(bool)deleteNode:(id)node
{
	if ( [node fatherNode] != nil )
	{
		if ( [[node fatherNode] count] == 1 )
			[self deleteNode:[node fatherNode]];
	}
	[node release];
	return true;
}
*/
-(void)searchNode:(NSArray*)py:(id)startNode:(NSString*)preWord
{
	id node;
	NSInteger i;
	NSArray* subArray = [py subarrayWithRange:NSMakeRange(1, [py count] - 1)];
	NSMutableArray* tmpstr = [[NSMutableArray alloc] init];;
	NSLog([@"searching node:" stringByAppendingString:[py objectAtIndex:0]]);
	NSLog(preWord);
	for ( node in [startNode childList] )
	{
		if ( [[node py] isEqualToString:[py objectAtIndex:0]] )
		{
			for ( i = 0; i<[[node word] count]; i++ )
			{
//				if ( [[[[node word] objectAtIndex:i] prevWord] count] > 0 )
//					NSLog( [[[[node word] objectAtIndex:i] prevWord] objectAtIndex:0] );
				if ( ( [[[[node word] objectAtIndex:i] prevWord] count] > 0 ) && ( preWord != nil ) )
					if ( [[[[node word] objectAtIndex:i] prevWord] indexOfObject:preWord] != NSNotFound )
					{
						NSLog(@"prevWord found!");
						[tmpstr insertObject:[[[node word] objectAtIndex:i] wordstr] atIndex:0];
					}
					else
						[tmpstr addObject:[[[node word] objectAtIndex:i] wordstr]];
				else
					[tmpstr addObject:[[[node word] objectAtIndex:i] wordstr]];
			}
			if ( [tmpstr count] >0 )
				[_candidatesPhases insertObjects:tmpstr atIndexes:[NSIndexSet indexSetWithIndexesInRange:(NSMakeRange(0, [tmpstr count]))]];
			if ( [py count] > 1 )
				[self searchNode:subArray:node:preWord];
		}
	}
}

-(void)sortCandidates
{
	//TODO
}

-(BOOL)searchTree:(NSArray*)py:(NSString*)preWord
{
	[_candidatesPhases removeAllObjects];
	[self searchNode:py:head:preWord];
	if ( [_candidatesPhases count] > 0 )
	{
//		[self sortCandidates];
		return true;
	}
	else
		return false;
}

-(NSInteger)editFreq:(NSArray*)py:(NSString*)word:(id)startNode
{
	ddIM_wordList* node;
	NSRange range;
	NSInteger i;
	range.location = 1;
	range.length = [py count] - 1;
	NSArray* subArray = [py subarrayWithRange:range];
	NSInteger originalIndex;
	NSInteger maxFreq;
	NSInteger originalFreq;
	NSInteger newFreq;
	bool objectAdded = false;
	ddIM_wordList* parent;
	if ( startNode == nil ) parent = head;
	else parent = startNode;
	ddIM_word* newWord = [[ddIM_word alloc] init];
	for ( node in [parent childList] )
	{
		if ( [[node py] isEqualToString:[py objectAtIndex:0]] )
		{
			if ( [py count] == 1 )
			{
				for ( i = 0; i<[[node word] count]; i++) //ddIM_word: wordstr;freq;prevWord
				{
					if ( [[[[node word] objectAtIndex:i] wordstr] isEqualToString:word] )
					{
						NSLog(@"found word!");
						originalFreq = [[[node word] objectAtIndex:i] freq];
						if ( i == 0 ) //if it is already the lasgest one
						{
							[[[node word] objectAtIndex:i] setFreq:originalFreq+1];
							return originalFreq+1;
						}
						originalIndex = i;
						[newWord setPrevWord:[NSMutableArray arrayWithArray:[[[node word] objectAtIndex:i] prevWord]]];
						[newWord setWordstr:[NSString stringWithString:word]];
						[[node word] removeObjectAtIndex:i];
						break;
					}
				}
				maxFreq = [[[node word] objectAtIndex:0] freq];
				if ( ( maxFreq - originalFreq ) / 2 == 0 )
					newFreq = originalFreq + 1;
				else
					newFreq = originalFreq + ( maxFreq - originalFreq ) / 2;
				[newWord setFreq:newFreq];
				for ( i = 0; i<[[node word] count]; i++)
				{
					if ( newFreq >= [[[node word] objectAtIndex:i] freq] )
					{
						[[node word] insertObject:newWord atIndex:i];
						objectAdded = true;
						break;
					}
				}
				if (!objectAdded) //if it is the smallest one, add it to the bottom
					[[node word] addObject:newWord];
				NSLog([NSString stringWithFormat:@"%d", newFreq]);
				NSLog([NSString stringWithFormat:@"%d", originalFreq]);
				return newFreq;
			}
			else
			{
				return [self editFreq:subArray:word:node];
			}
		}
	}
}

-(NSMutableArray*)candidatesPhases
{
	return _candidatesPhases;
}

-(NSMutableArray*)candidatesPY
{
	return _candidatesPY;
}

-(void)dealloc
{
	[head release];
	[_candidatesPhases release];
	[_candidatesPY release];
	[super dealloc];
}

@end
